package com.hyper_yang.algorithmRecord;

import java.util.ArrayList;
import java.util.List;

// 找到字符串中所有字母的异位词
public class LeetCode_438 {
    /*
        给定两个字符串 s和 p，找到 s中【所有】 p的异位词的子串，
        返回这些子串的起始索引。不考虑答案输出的顺序。
        字母异位词: 字母相同，但排列不同的字符串。
     */

    // 方法一: 暴力法，枚举  O(m * n)
    public static List<Integer> findAnagrams1(String s, String p) {
        // 定义结果列表
        List<Integer> res = new ArrayList<>();
        // 统计 p中所有字符频次
        int[] pCounts = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pCounts[p.charAt(i) - 'a']++;
        }
        // 遍历 s,考察长度为 p.length()的字串
        for (int i = 0; i < s.length() - p.length() + 1; i++) {
            // 判断 子串是否满足 异位词标准
            boolean isMatched = true;
            // 统计子串中所有字符
            int[] subCounts = new int[26];
            for (int j = i; j < i + p.length(); j++) {
                subCounts[s.charAt(j) - 'a']++;
                int index = s.charAt(j) - 'a';
                // 如果，字符频次超过了p中的频次，则一定不符合要求
                if (subCounts[index] > pCounts[index]) {
                    isMatched = false;
                    break;
                }
            }
            if (isMatched) res.add(i);
        }
        return res;
    }

    // 方法二: 滑动窗口法 O(n)
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        // 统计 p中所有字符频次
        int[] pCounts = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pCounts[p.charAt(i) - 'a']++;
        }
        // 统计子串频率
        int[] subCounts = new int[26];
        // 定义起始、结束位置
        int start = 0, end = 1;
        while (end <= s.length()) {
            // 末尾新增
            char newChar = s.charAt(end - 1);
            subCounts[newChar - 'a']++;
            // 判断是否满足异位词标准 (考虑新增字符的影响)
            while (subCounts[newChar - 'a'] > pCounts[newChar - 'a'] && start < end) {
                char removedChar = s.charAt(start);
                subCounts[removedChar - 'a']--;
                start++;
            }
            if (end - start == p.length()) res.add(start);
            end++;
        }
        return res;
    }

    public static void main(String[] args) {
        for (int i : findAnagrams("cbaebabacd", "abc")) {
            System.out.print(i + "\t");
        }
        System.out.println();
        for (int i : findAnagrams("abab", "ab")) {
            System.out.print(i + "\t");
        }
    }
}
